package main

func numDecodings(s string) int {
	if len(s) == 0 {
		return 1
	}
	dp := make([]int, len(s)+1)
	dp[0] = 1
	for i, c := range s {
		i++
		if i == 1 {
			if c != '0' {
				dp[i] = 1
			}
		} else {
			a := s[i-2] - '0'
			b := s[i-1] - '0'
			v := 10*a + b
			if b != 0 {
				dp[i] += dp[i-1]
			}
			if a != 0 && v <= 26 {
				dp[i] += dp[i-2]
			}
		}
	}
	return dp[len(s)]
}

func main() {
	//println(numDecodings("12"))
	//println(numDecodings("226"))
	//println(numDecodings("106"))
	//println(numDecodings("06"))
	//println(numDecodings("160"))
	//println(numDecodings("1601"))
	println(numDecodings("2101"))
}
